Сегментна дрвета

Видели смо да низ збирова префикса, омогућава ефикасно постављање упита над сегментима низа, али не омогућава ефикасно ажурирање елемената низа, јер је потребно ажурирати све збирове префикса након ажурираног елемента, што је нарочито неефикасно када се ажурирају елементи близу почетка низа (сложеност најгорег случаја је \(O(n)\)). Низ разлика суседних елемената допушта стална ажурирања низа, међутим, извршавање упита очитавања стања низа подразумева реконструкцију низа, што је сложености \(O(n)\).

Разматраћемо проблеме у којима је потребно да се упити ажурирања низа и очитавања његових статистика јављају испреплетано. За разлику од претходних, статичких упита над распонима (енгл. static range queries), овде ћемо разматрати тзв. динамичке упите над распонима (енгл. dynamic range queries), тако да је потребно развити напредније структуре података које омогућавају извршавање оба типа упита ефикасно. На пример, размотримо прoблем имплементације структуре података која обезбеђује ефикасно израчунавање збирова сегмената датог низа одређених интервалима позиција \([a, b]\), при чему се појединачни елементи низа могу често мењати.

У наставку ћемо видети две различите, али донекле сличне структуре података које дају ефикасно решење претходног проблема и њему сличних.

Једна структура података која омогућава прилично једноставно и ефикасно решавање овог проблема су сегментна дрвета. Опет се током фазе препроцесирања израчунавају збирови одређених сегмената полазног низа, а онда се збир елемената произвољног сегмента полазног низа изражава у функцији тих унапред израчунатих збирова.Рецимо и да сегментна дрвета нису специфична само за сабирање, већ се могу користити и за друге статистике сегмената које се израчунавају асоцијативним операцијама (на пример за одређивање најмањег или највећег елемента, нзд-а свих елемената и слично).

Претпоставимо да је дужина низа степен броја 2 (ако није, низ се може допунити до најближег степена броја 2, најчешће нулама). Чланови низа представљају листове дрвета. Групишемо два по два суседна чвора и на сваком наредном нивоу дрвета чувамо родитељске чворове који чувају збирове своја два детета. Ако је дат низ \(3, 4, 1, 2, 6, 5, 1, 4\), сегментно дрво за збирове изгледа овако.

              26
      10              16
  7       3       11      5
3   4   1   2   6   5   1   4

Пошто је дрво потпуно, најједноставнија имплементација је да се чува имплицитно у низу (слично као у случају хипа). Претпоставићемо да елементе дрвета смештамо од позиције \(1\), јер је тада аритметика са индескима мало једноставнија (елементи полазног низа могу бити индексирани класично, кренувши од нуле).

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
-  26 10 16 7  3  11 5  3  4  1  2  6  5  1  4 

Уочимо неколико карактеристика овог начина смештања. Корен је смештен на позицији 1. Елементи полазног низа налазе се на позицијама \([n,2n-1]\). Елемент који се у полазном низу налази на позицији \(p\), се у сегментном дрвету налази на позицији \(p+n\). Лево дете чвора \(k\) налази се на позицији \(2k\), а десно на позицији \(2k+1\). Дакле, на парним позицијама се налазе лева деца својих родитеља, а на непарним десна. Родитељ чвора \(k\) налази се на позицији \(\lfloor{\frac{k}{2}}\rfloor\).

Размотримо сада како бисмо нашли збир елемената на позицијама из сегмента \([2, 6]\), тј. збир елемената \(1, 2, 6, 5, 1\). У сегментном дрвету тај сегмент је смештен на позицијама \([2+8, 6+8] = [10,14]\). Збир прва два елемента (\(1, 2\)) се налази у чвору изнад њих, збир наредна два елемента (\(6, 5\)) такође, док се у родитељском чвору елемента \(1\) налази његов збир са елементом \(4\), који не припада сегменту који сабирамо. Зато збир елемената на позицијама \([10, 14]\) у сегментном дрвету можемо разложити на збир елемената на позицијама \([5, 6]\) и елемента на позицији \(14\).

Размотримо и како бисмо рачунали збир елемената на позицијама из сегмента \([3, 7]\), тј. збир елемената \(2, 6, 5, 1, 4\). У сегментном дрвету тај сегмент је смештен на позицијама \([3+8, 7+8] = [11, 15]\). У родитељском чвору елемента \(2\) налази се његов збир са елементом \(1\) који не припада сегменту који сабирамо. Збирови елемената \(6\) и \(5\) и елемената \(1\) и \(4\) се налазе у чворовима иза њих, а збир сва четири дата елемента у чвору изнад њих.

Уместо операције којом се мења члану низа на позицији \(i\) додељује вредност \(v\), често се разматра функција која елемент низа на позицији \(i\) полазног низа увећава за дату вредност \(v\) и у складу са тим ажурира сегментно дрво. Свака од ове две функције се лако изражава преко оне друге.

Имплементација сегментног дрвета за друге асоцијативне операције је скоро идентична, осим што се оператор + мења другом операцијом.